package bst_ai;

public class BST_AI {
	public class BinarySearchTree<T> {
	    private Node root;

	    private class Node {
	        T data;
	        Node left;
	        Node right;

	        Node(T data) {
	            this.data = data;
	            this.left = null;
	            this.right = null;
	        }
	    }

	    public BinarySearchTree() {
	        this.root = null;
	    }

	    // 插入方法
	    public boolean insert(T obj) {
	        if (obj == null) {
	            throw new IllegalArgumentException("Cannot insert null value");
	        }
	        if (root == null) {
	            root = new Node(obj);
	            return true;
	        } else {
	            return insertRec(root, obj);
	        }
	    }

	    private boolean insertRec(Node node, T obj) {
	        int cmp = obj.compareTo(node.data);
	        if (cmp < 0) {
	            if (node.left == null) {
	                node.left = new Node(obj);
	                return true;
	            } else {
	                return insertRec(node.left, obj);
	            }
	        } else if (cmp > 0) {
	            if (node.right == null) {
	                node.right = new Node(obj);
	                return true;
	            } else {
	                return insertRec(node.right, obj);
	            }
	        } else {
	            // 如果值已经存在，不进行插入操作
	            return false;
	        }
	    }

	    // 搜索方法
	    public boolean search(T obj) {
	        if (obj == null) {
	            throw new IllegalArgumentException("Cannot search for null value");
	        }
	        return searchRec(root, obj);
	    }

	    private boolean searchRec(Node node, T obj) {
	        if (node == null) {
	            return false;
	        }
	        int cmp = obj.compareTo(node.data);
	        if (cmp < 0) {
	            return searchRec(node.left, obj);
	        } else if (cmp > 0) {
	            return searchRec(node.right, obj);
	        } else {
	            return true; // 找到匹配的值
	        }
	    }

	    // 访问方法（中序遍历）
	    public void visit() {
	        inOrderTraversal(root);
	    }

	    private void inOrderTraversal(Node node) {
	        if (node != null) {
	            inOrderTraversal(node.left);
	            System.out.println(node.data);
	            inOrderTraversal(node.right);
	        }
	    }
	}

}
